// 左叶子节点的定义：节点A的左节点不为空，且左节点的左右子节点都为空，叶子节点 

// 思路1：前序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小
function sumOfLeftLeaves(root) {
    if (!root) {
        return 0
    }
    let val = 0
    if (root.left && !root.left.left && !root.left.right) {
        val = root.left.val
    }
    return val + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right)
}

// 思路2：迭代
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，stack的大小
function sumOfLeftLeaves2(root) {
    if (!root) {
        return 0
    }
    let queue = [root]
    let res = 0
    while (queue.length) {
        let node = queue.pop()
        if (node.left && !node.left.left && !node.left.right) {
            res += node.left.val
        }
        if (node.right) {
            queue.push(node.right)
        }
        if (node.left) {
            queue.push(node.left)
        }
    }
    return res
}


const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
        },
    },
    right: {
        val: 6,
    },
};

console.log(sumOfLeftLeaves(root))
console.log(sumOfLeftLeaves2(root))